{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Substrings That Differ by One Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计只差一个字符的子串数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;，请你找出 <code>s</code>&nbsp;中的非空子串的数目，这些子串满足替换 <strong>一个不同字符</strong>&nbsp;以后，是 <code>t</code>&nbsp;串的子串。换言之，请你找到 <code>s</code>&nbsp;和 <code>t</code>&nbsp;串中 <strong>恰好</strong>&nbsp;只有一个字符不同的子字符串对的数目。</p>\n",
    "\n",
    "<p>比方说，&nbsp;<code>\"<u>compute</u>r\"</code>&nbsp;and&nbsp;<code>\"<u>computa</u>tion\"&nbsp;</code>只有一个字符不同：&nbsp;<code>'e'</code>/<code>'a'</code>&nbsp;，所以这一对子字符串会给答案加 1 。</p>\n",
    "\n",
    "<p>请你返回满足上述条件的不同子字符串对数目。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong>&nbsp;是一个字符串中连续的字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aba\", t = \"baba\"\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>以下为只相差 1 个字符的 s 和 t 串的子字符串对：\n",
    "(\"<strong>a</strong>ba\", \"<strong>b</strong>aba\")\n",
    "(\"<strong>a</strong>ba\", \"ba<strong>b</strong>a\")\n",
    "(\"ab<strong>a</strong>\", \"<strong>b</strong>aba\")\n",
    "(\"ab<strong>a</strong>\", \"ba<strong>b</strong>a\")\n",
    "(\"a<strong>b</strong>a\", \"b<strong>a</strong>ba\")\n",
    "(\"a<strong>b</strong>a\", \"bab<strong>a</strong>\")\n",
    "加粗部分分别表示 s 和 t 串选出来的子字符串。\n",
    "</pre>\n",
    "<strong>示例 2：</strong>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"ab\", t = \"bb\"\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>以下为只相差 1 个字符的 s 和 t 串的子字符串对：\n",
    "(\"<strong>a</strong>b\", \"<strong>b</strong>b\")\n",
    "(\"<strong>a</strong>b\", \"b<strong>b</strong>\")\n",
    "(\"<strong>ab</strong>\", \"<strong>bb</strong>\")\n",
    "加粗部分分别表示 s 和 t 串选出来的子字符串。\n",
    "</pre>\n",
    "<strong>示例 3：</strong>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"a\", t = \"a\"\n",
    "<b>输出：</b>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abe\", t = \"bbc\"\n",
    "<b>输出：</b>10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-substrings-that-differ-by-one-character](https://leetcode.cn/problems/count-substrings-that-differ-by-one-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-substrings-that-differ-by-one-character](https://leetcode.cn/problems/count-substrings-that-differ-by-one-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aba\"\\n\"baba\"', '\"ab\"\\n\"bb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1 - m, n):  # d=i-j, j=i-d\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i < n and i - d < m:\n",
    "                if s[i] != t[i - d]:\n",
    "                    k0 = k1  # 上上一个不同\n",
    "                    k1 = i   # 上一个不同\n",
    "                ans += k1 - k0\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            for j, y in enumerate(t):\n",
    "                if x == y:\n",
    "                    continue\n",
    "                l, r = 1, 1\n",
    "                while i-l >= 0 and j-l >= 0 and s[i-l] == t[j-l]:\n",
    "                    l += 1\n",
    "                while i+r < len(s) and j+r < len(t) and s[i+r] == t[j+r]:\n",
    "                    r += 1\n",
    "                ans += l * r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        sn,tn=len(s),len(t)\n",
    "        ans=0\n",
    "        for i in range(sn):\n",
    "            for j in range(tn):\n",
    "                a,b=s[i],t[j]\n",
    "                if a!=b:\n",
    "                    la=i-1\n",
    "                    ra=i+1\n",
    "                    lb=j-1\n",
    "                    rb=j+1\n",
    "                    while la>=0 and lb>=0 and s[la]==t[lb]:\n",
    "                        la-=1\n",
    "                        lb-=1\n",
    "                    while ra<sn and rb<tn and s[ra]==t[rb]:\n",
    "                        rb+=1\n",
    "                        ra+=1\n",
    "                    ans+=(i-la)*(ra-i)\n",
    "                    # print(la)\n",
    "                    # print(ra)\n",
    "                    # print(ans)\n",
    "                    # print(\"----------\")\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        #注意子字符串，必须是连续的\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1-m, n):\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i<n and i-d<m:\n",
    "                if s[i] != t[i-d]:\n",
    "                    k0 = k1\n",
    "                    k1 = i\n",
    "                ans += k1-k0\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        sn,tn=len(s),len(t)\n",
    "        ans=0\n",
    "        for i in range(sn):\n",
    "            for j in range(tn):\n",
    "                w=0\n",
    "                for k in range(min(sn-i,tn-j)):\n",
    "                    if s[i+k]!=t[j+k]:\n",
    "                        w+=1\n",
    "                    if w==1:\n",
    "                        ans+=1\n",
    "                    elif w>1:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        # 暴力\n",
    "        # cnts = Conter(s)\n",
    "        cntt = Counter(t)\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            left = i\n",
    "            right = i\n",
    "            while right<m:\n",
    "                cnt = (right-left+1)\n",
    "                right += 1\n",
    "                if cnt == 1:\n",
    "                    ans += n-cntt[s[i]]\n",
    "                    continue\n",
    "                tmp = s[left:right+1]\n",
    "                for j in range(n-cnt+1):\n",
    "                    cha = 0\n",
    "                    for k in range(cnt):\n",
    "                        # print(cnt,tmp,k,j,cha)\n",
    "                        if tmp[k] != t[j+k]:\n",
    "                            cha += 1\n",
    "                    if cha == 1:\n",
    "                        ans +=1\n",
    "        return ans\n",
    "                            \n",
    "                        \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i+k] != t[j+k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        ans = 0\n",
    "        for k in range(1, n + 1):\n",
    "            for i in range(n - k + 1):\n",
    "                for j in range(m - k + 1):\n",
    "                    if sum(a!=b for a, b in zip(t[i:i+k], s[j:j+k])) == 1:\n",
    "                        ans += 1\n",
    "                    # print(k, i, j, t[i:i+k], s[j:j+k], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    中心点枚举\n",
    "    遍历找s[i] != t[j] 的情况，假设将这两个字符调整一次变为一样，那么往左边一共有多长的相同，往右边一共有多长的相同，\n",
    "    再套用公式 (left + 1) * (right + 1) 进行累加\n",
    "    为什么left + 1和right + 1，我理解left是不包括s[i] != t[j]的左侧连续的部分，左边有几个就是几，但是可能左侧一个\n",
    "    都不选，也是一种可能，所以要left + 1， 同理，右侧也是一样的，所以最终是左右两边都加一再相乘\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    continue\n",
    "                \n",
    "                ks, kt = i - 1, j - 1\n",
    "                left = 0\n",
    "                while ks >= 0 and kt >= 0:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    left += 1\n",
    "                    ks -= 1\n",
    "                    kt -= 1\n",
    "                \n",
    "                ks, kt = i + 1, j + 1\n",
    "                right = 0\n",
    "                while ks < m and kt < n:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    right += 1\n",
    "                    ks += 1\n",
    "                    kt += 1\n",
    "                \n",
    "                res += (left + 1) * (right + 1)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            for j, y in enumerate(t):\n",
    "                if x == y:\n",
    "                    continue\n",
    "                l, r = 1, 1\n",
    "                while i-l >= 0 and j-l >= 0 and s[i-l] == t[j-l]:\n",
    "                    l += 1\n",
    "                while i+r < len(s) and j+r < len(t) and s[i+r] == t[j+r]:\n",
    "                    r += 1\n",
    "                ans += l * r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                for k in range(min(len(s)-i, len(t)-j)):\n",
    "                    if s[i+k] != t[j+k]: diff += 1\n",
    "                    res += (diff==1)\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1 - m, n):  # d=i-j, j=i-d\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i < n and i - d < m:\n",
    "                if s[i] != t[i - d]:\n",
    "                    k0 = k1  # 上上一个不同\n",
    "                    k1 = i   # 上一个不同\n",
    "                ans += k1 - k0\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/count-substrings-that-differ-by-one-character/solutions/2192600/tu-jie-fei-bao-li-onm-suan-fa-pythonjava-k5og/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s) + 1):\n",
    "                length = j - i\n",
    "                for k in range(len(t) - length + 1):\n",
    "                    if self.check(s[i:j], t[k:k + length]):\n",
    "                        ans += 1\n",
    "        return ans\n",
    "\n",
    "    def check(self, s0, s1):\n",
    "        diff = 0\n",
    "        for i in range(len(s0)):\n",
    "            if s0[i] != s1[i]:\n",
    "                diff += 1\n",
    "                if diff >= 2:\n",
    "                    return False\n",
    "        return True if diff == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n1, n2 = 0, len(s), len(t)\n",
    "        for i in range(n1):\n",
    "            for j in range(n2):\n",
    "                if s[i] != t[j]:\n",
    "                    left = 0\n",
    "                    for l in range(1, min(i,j)+1):\n",
    "                        if s[i-l] == t[j-l]:\n",
    "                            left += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    right = 0\n",
    "                    for r in range(1, min(n1-i, n2-j)):\n",
    "                        if s[i+r] == t[j+r]:\n",
    "                            right += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    ans += (1+left) * (1+right)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            for j, y in enumerate(t):\n",
    "                if x == y:\n",
    "                    continue\n",
    "                l, r = 1, 1\n",
    "                while i-l >= 0 and j-l >= 0 and s[i-l] == t[j-l]:\n",
    "                    l += 1\n",
    "                while i+r < len(s) and j+r < len(t) and s[i+r] == t[j+r]:\n",
    "                    r += 1\n",
    "                ans += l * r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        def check(s1, s2):\n",
    "            num = 0\n",
    "            for ii in range(len(s1)):\n",
    "                if s1[ii] != s2[ii]:\n",
    "                    num += 1\n",
    "                    if num >= 2:\n",
    "                        return False\n",
    "            return num == 1\n",
    "\n",
    "        ans = 0\n",
    "        for length in range(1, len(s) + 1):\n",
    "            cache = {}\n",
    "            for i in range(len(s) - length + 1):\n",
    "                # 获取当前字符串\n",
    "                pattern = s[i:i + length]\n",
    "\n",
    "                # 如果没被计算过，则遍历t计算\n",
    "                if pattern not in cache:\n",
    "                    num = 0\n",
    "                    for j in range(len(t) - length + 1):\n",
    "                        if check(pattern, t[j:j + length]):\n",
    "                            num += 1\n",
    "                    cache[pattern] = num\n",
    "\n",
    "                # 累加当前结果到答案\n",
    "                # print(pattern, \":\", cache[pattern])\n",
    "                ans += cache[pattern]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 注意计算结果复用，减少计算量\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1 - m, n): # d = i - j, j = i - d\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i < n and i - d < m:\n",
    "                if s[i] != t[i - d]: # 子串结果比对\n",
    "                    k0 = k1 # 上上一个不同\n",
    "                    k1 = i # 上一个不同\n",
    "                ans += k1 - k0 # 前后缀分解\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 注意计算结果复用，减少计算量\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1 - m, n): # d = i - j, j = i - d\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i < n and i - d < m:\n",
    "                if s[i] != t[i - d]:\n",
    "                    k0 = k1 # 上上一个不同\n",
    "                    k1 = i # 上一个不同\n",
    "                ans += k1 - k0\n",
    "                i += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff, k = 0, 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    diff += (s[i + k] != t[j + k])\n",
    "                    if diff > 1:\n",
    "                        break\n",
    "                    ans += (diff == 1)\n",
    "                    k += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        s_len, t_len = len(s), len(t)\n",
    "        for i in range(s_len):\n",
    "            for j in range(t_len):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    中心点枚举\n",
    "    遍历找s[i] != t[j] 的情况，假设将这两个字符调整一次变为一样，那么往左边一共有多长的相同，往右边一共有多长的相同，\n",
    "    再套用公式 (left + 1) * (right + 1) 进行累加\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    continue\n",
    "                \n",
    "                ks, kt = i - 1, j - 1\n",
    "                left = 0\n",
    "                while ks >= 0 and kt >= 0:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    left += 1\n",
    "                    ks -= 1\n",
    "                    kt -= 1\n",
    "                \n",
    "                ks, kt = i + 1, j + 1\n",
    "                right = 0\n",
    "                while ks < m and kt < n:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    right += 1\n",
    "                    ks += 1\n",
    "                    kt += 1\n",
    "                \n",
    "                res += (left + 1) * (right + 1)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    continue\n",
    "                \n",
    "                ks, kt = i - 1, j - 1\n",
    "                left = 0\n",
    "                while ks >= 0 and kt >= 0:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    left += 1\n",
    "                    ks -= 1\n",
    "                    kt -= 1\n",
    "                \n",
    "                ks, kt = i + 1, j + 1\n",
    "                right = 0\n",
    "                while ks < m and kt < n:\n",
    "                    if s[ks] != t[kt]:\n",
    "                        break\n",
    "                    right += 1\n",
    "                    ks += 1\n",
    "                    kt += 1\n",
    "                \n",
    "                res += (left + 1) * (right + 1)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans, n, m = 0, len(s), len(t)\n",
    "        for d in range(1 - m, n):  # d=i-j, j=i-d\n",
    "            i = max(d, 0)\n",
    "            k0 = k1 = i - 1\n",
    "            while i < n and i - d < m:\n",
    "                if s[i] != t[i - d]:\n",
    "                    k0 = k1  # 上上一个不同\n",
    "                    k1 = i   # 上一个不同\n",
    "                ans += k1 - k0\n",
    "                i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        n1=len(s)\n",
    "        n2=len(t)\n",
    "        ans=0\n",
    "        for i in range(n1):\n",
    "            for j in range(n2):\n",
    "                cnt=0\n",
    "                for k in range(min(n1-i,n2-j)):\n",
    "                    if s[i+k]!=t[j+k]:\n",
    "                        cnt+=1\n",
    "                    if cnt==1:\n",
    "                        ans+=1\n",
    "                    elif cnt>1:\n",
    "                        break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while (i + k) < len(s) and (j + k) < len(t):\n",
    "                    if s[i+k] != t[j +k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        res += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                diff = 0\n",
    "                k = 0\n",
    "                while i + k < len(s) and j + k < len(t):\n",
    "                    if s[i + k] != t[j + k]:\n",
    "                        diff += 1\n",
    "                    if diff == 1:\n",
    "                        ans += 1\n",
    "                    elif diff > 1:\n",
    "                        break\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        #dpl[i][j]表示以s[i-1] t[j-1]终点左连续最长公共子序列\n",
    "        dpl = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        #dpr[i][j]表示以s[i-1] t[j-1]起点右连续最长公共子序列\n",
    "        dpr = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    dpl[i][j]=dpl[i-1][j-1]+1\n",
    "                else:\n",
    "                    dpl[i][j]=0\n",
    "\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]==t[j]:\n",
    "                    dpr[i][j]=dpr[i+1][j+1]+1\n",
    "                else:\n",
    "                    dpr[i][j]=0\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i]!=t[j]:\n",
    "                    ans+=(dpl[i][j]+1)*(dpr[i+1][j+1]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m,n=len(s), len(t)\n",
    "        dpSame, dpDiff1= [n*[0] for _ in range(m)], [n*[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            if s[i]==t[0]: dpSame[i][0]=1\n",
    "            else: dpDiff1[i][0]=1\n",
    "        for j in range(n):\n",
    "            if s[0]==t[j]: dpSame[0][j]=1\n",
    "            else: dpDiff1[0][j]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if s[i]==t[j]:\n",
    "                    dpSame[i][j]=1+dpSame[i-1][j-1]\n",
    "                    dpDiff1[i][j]=dpDiff1[i-1][j-1]\n",
    "                else:\n",
    "                    dpDiff1[i][j]=1+dpSame[i-1][j-1]\n",
    "        S=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                S+=dpDiff1[i][j]\n",
    "        return S\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dpl[i][j]表示以s[i]和t[j]为终点，左侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    dpr[i][j]表示以s[i]和t[j]为终点，右侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    举个例子\n",
    "    a b b d a\n",
    "    a b c d b\n",
    "    dpl[2][2] = 2 -> a b\n",
    "    dpr[2][2] = 1 -> d\n",
    "    都不包括下标2的那个不同的\n",
    "    那么如果存在某个下标对应不同字符，左右两边共有 (dpl[i][j] + 1) * (dpr[i][j] + 1) 个不同数目\n",
    "    ** 可以简单将公式理解成左边，包括只有不同的那一对字符，共有dpl[i][j] + 1种组合，右边共有dpr[i][j] + 1种组合，合起来就是乘积的关系 **\n",
    "    如何计算dpl[i][j]、dpr[i][j]?\n",
    "    这个比较简单，如果当前遍历到的s[i] == t[j]，那么就可以延续dp[i - 1][j - 1]、dp[i + 1][j + 1]的长度，否则就清零\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        '''\n",
    "        因为当前状态要从左侧推导出来，所以左边要留一个初始状态值dp[0][0]\n",
    "        '''\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dpl[i + 1][j + 1] = dpl[i][j] + 1\n",
    "        ''' \n",
    "        同理，要从右边推导状态，右边也需要留一个初始状态dp[-1][-1]，定义dp长度为m + 1和n + 1\n",
    "        所以，按照原始数组长度正常遍历就行\n",
    "        ''' \n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i][j] = dpr[i + 1][j + 1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    '''\n",
    "                    注意dpl[i][j]正好是不包括s[i]和t[j]的，因为dpl是左偏移的，dpr则需要加一，因为要去掉\n",
    "                    '''\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dpl[i + 1][j + 1] = dpl[i][j] + 1\n",
    "        \n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i][j] = dpr[i + 1][j + 1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dpl[i][j] = dpl[i - 1][j - 1] + 1\n",
    "                \n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i][j] = dpr[i + 1][j + 1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        #dpl[i][j]表示以s[i-1] t[j-1]终点左连续最长公共子序列\n",
    "        dpl = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        #dpr[i][j]表示以s[i-1] t[j-1]起点右连续最长公共子序列\n",
    "        dpr = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    dpl[i][j]=dpl[i-1][j-1]+1\n",
    "                else:\n",
    "                    dpl[i][j]=0\n",
    "\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]==t[j]:\n",
    "                    dpr[i][j]=dpr[i+1][j+1]+1\n",
    "                else:\n",
    "                    dpr[i][j]=0\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i]!=t[j]:\n",
    "                    ans+=(dpl[i][j]+1)*(dpr[i+1][j+1]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dpl[i + 1][j + 1]表示以s[i]和t[j]为终点，左侧最长的连续相同子数组长度，其中\"包括\"s[i]和t[j]本身，加一是因为从左到右遍历时需要从i -> i + 1 得有第一位的初始值\n",
    "    dpr[i][j]表示以s[i]和t[j]为终点，右侧最长的连续相同子数组长度，其中\"包括\"s[i]和t[j]本身，这个和dpl不同不需要减一是因为，\n",
    "    dpr的初始值是在最右侧多一位，i、j就和s[i]、t[j]直接对应\n",
    "    ** 注意这个定义和官方解答不同，官解写的有问题，定义与递推公式不匹配，这里是匹配的 **\n",
    "    那么如果存在某个下标对应不同字符，左右两边共有 (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1) 个不同数目\n",
    "    因为dpl i + 1对应s中的i，所以dpl[i][j] 实际上是对应s中的i - 1，dpr是和s下标完全对应的，所以s[i] != t[j]时，需要往右移一个\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dpl[i + 1][j + 1] = dpl[i][j] + 1\n",
    "\n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i][j] = dpr[i + 1][j + 1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        # a,b的范围都只有100\n",
    "        # 在枚举一个子串的时候,如果能在O(n)的时间内找到与之\n",
    "        # 反向思考,最长相等前缀\n",
    "\n",
    "        max_pre = [[0]*len(t) for _ in range(len(s))] \n",
    "        max_tail = [[0]*len(t) for _ in range(len(s))]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                # 求前缀\n",
    "                count = 0\n",
    "                for pre in range(min(i,j)+1):\n",
    "                    if s[i-pre] == t[j-pre]:\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        break\n",
    "                max_pre[i][j] = count \n",
    "                # 求后缀\n",
    "                count = 0\n",
    "                for pre in range(min(len(s)-i,len(t)-j)):\n",
    "                    if s[i+pre] == t[j+pre]:\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        break \n",
    "                max_tail[i][j] = count\n",
    "\n",
    "        # 枚举是那两个字母不一致\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(t)):\n",
    "                if s[i] != t[j]:\n",
    "                    res += 1\n",
    "                    # 看前缀\n",
    "                    if i >= 1 and j >= 1: \n",
    "                        res += max_pre[i-1][j-1]\n",
    "                    # 看后缀\n",
    "                    if i+1 < len(s) and j+1 < len(t):\n",
    "                        res += max_tail[i+1][j+1]\n",
    "                    if i >= 1 and j >= 1 and i+1 < len(s) and j+1 < len(t):\n",
    "                        res += max_pre[i-1][j-1] * max_tail[i+1][j+1] \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        dpl = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        dpr = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dpl[i][j] = dpl[i - 1][j - 1] + 1\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i][j] = dpr[i + 1][j + 1] + 1\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    res += (dpl[i][j] + 1)*(dpr[i + 1][j + 1] + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dpl[i][j]表示以s[i]和t[j]为终点，左侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    dpr[i][j]表示以s[i]和t[j]为终点，右侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    举个例子\n",
    "    a b b d a\n",
    "    a b c d b\n",
    "    dpl[2][2] = 2 -> a b\n",
    "    dpr[2][2] = 1 -> d\n",
    "    都不包括下标2的那个不同的，当然如果下标2相同也不管，依然是dpl[2][2] = 2\n",
    "    那么如果存在某个下标对应不同字符，左右两边共有 (dpl[i][j] + 1) * (dpr[i][j] + 1) 个不同数目\n",
    "    ** 可以简单将公式理解成左边，包括只有不同的那一对字符，共有dpl[i][j] + 1种组合，右边共有dpr[i][j] + 1种组合，合起来就是乘积的关系 **\n",
    "    如何计算dpl[i][j]、dpr[i][j]?\n",
    "    这个比较简单，如果当前遍历到的s[i] == t[j]，那么就可以延续dp[i - 1][j - 1]、dp[i + 1][j + 1]的长度，否则就清零\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        '''\n",
    "        因为当前状态要从左侧推导出来，所以左边要留一个初始状态值dp[0][0]\n",
    "        有一个细节需要注意，dpl[i][j]按照定义是不包括s[i]和t[j]的，所以dpl[i][j]的推导不能直接通过s[i]和t[j]是否相同计算，\n",
    "        因为和s[i]和t[j]没有关系，(i, j) -> (i + 1, j + 1)\n",
    "        '''\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dpl[i + 1][j + 1] = dpl[i][j] + 1\n",
    "        ''' \n",
    "        同理，要从右边推导状态，右边也需要留一个初始状态dp[-1][-1]\n",
    "        同样的，按照定义dpr[i][j]不包括s[i]和t[j]，所以(i, j) -> (i - 1, j - 1)，为了满足i - 1, j - 1,只能遍历到0，\n",
    "        对于第一个元素，由于dpr[0][0]是不关心s[0]和t[0]的，所以都不用比较是否相等，s[0]和t[0]的比较由dpl去完成\n",
    "        ''' \n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, 0, -1):\n",
    "            for j in range(n - 1, 0, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i - 1][j - 1] = dpr[i][j] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    '''\n",
    "                    由于dpl和dpr严格按照定义进行，就可以套用公式，否则就会出现官解答案里各种稀奇古怪的+1\n",
    "                    '''\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i][j] + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dpl[i][j]表示以s[i]和t[j]为终点，左侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    dpr[i][j]表示以s[i]和t[j]为终点，右侧最长的连续相同子数组长度，其中不包括s[i]和t[j]本身\n",
    "    举个例子\n",
    "    a b b d a\n",
    "    a b c d b\n",
    "    dpl[2][2] = 2 -> a b\n",
    "    dpr[2][2] = 1 -> d\n",
    "    都不包括下标2的那个不同的\n",
    "    那么如果存在某个下标对应不同字符，左右两边共有 (dpl[i][j] + 1) * (dpr[i][j] + 1) 个不同数目\n",
    "    ** 可以简单将公式理解成左边，包括只有不同的那一对字符，共有dpl[i][j] + 1种组合，右边共有dpr[i][j] + 1种组合，合起来就是乘积的关系 **\n",
    "    如何计算dpl[i][j]、dpr[i][j]?\n",
    "    这个比较简单，如果当前遍历到的s[i] == t[j]，那么就可以延续dp[i - 1][j - 1]、dp[i + 1][j + 1]的长度，否则就清零\n",
    "    '''\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        '''\n",
    "        因为当前状态要从左侧推导出来，所以左边要留一个初始状态值dp[0][0]\n",
    "        '''\n",
    "        dpl = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dpl[i + 1][j + 1] = dpl[i][j] + 1\n",
    "        ''' \n",
    "        同理，要从右边推导状态，右边也需要留一个初始状态dp[-1][-1]，定义dp长度为m + 1和n + 1\n",
    "        所以，按照原始数组长度正常遍历就行\n",
    "        ''' \n",
    "        dpr = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, 0, -1):\n",
    "            for j in range(n - 1, 0, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dpr[i - 1][j - 1] = dpr[i][j] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] != t[j]:\n",
    "                    '''\n",
    "                    注意dpl[i][j]正好是不包括s[i]和t[j]的，因为dpl是左偏移的，dpr则需要加一，因为要去掉\n",
    "                    '''\n",
    "                    res += (dpl[i][j] + 1) * (dpr[i][j] + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        cnt = dict()\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                cnt[t[i:j+1]] = cnt.get(t[i:j+1], 0) + 1\n",
    "        ans = 0\n",
    "        word = [chr(ord(\"a\")+i) for i in range(26)]\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                st = s[i:j+1]\n",
    "                k = len(st)\n",
    "                for x in range(k):\n",
    "                    for w in word:\n",
    "                        if w != st[x]:\n",
    "                            ans += cnt.get(st[:x]+w+st[x+1:], 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m,n = len(s), len(t)\n",
    "        dp = [[[0]*2 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i+1][j+1][0] = dp[i][j][0] + 1\n",
    "                    dp[i+1][j+1][1] = dp[i][j][1]\n",
    "                else:\n",
    "                    dp[i+1][j+1][1] = dp[i][j][0] + 1\n",
    "                ans += dp[i+1][j+1][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m,n = len(s), len(t)\n",
    "        dp = [[[0]*2 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i+1][j+1][0] = dp[i][j][0] + 1\n",
    "                    dp[i+1][j+1][1] = dp[i][j][1]\n",
    "                else:\n",
    "                    dp[i+1][j+1][1] = dp[i][j][0] + 1\n",
    "                ans += dp[i+1][j+1][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        m,n = len(s), len(t)\n",
    "        dp = [[[0]*2 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i+1][j+1][0] = dp[i][j][0] + 1\n",
    "                    dp[i+1][j+1][1] = dp[i][j][1]\n",
    "                else:\n",
    "                    dp[i+1][j+1][1] = dp[i][j][0] + 1\n",
    "                ans += dp[i+1][j+1][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str, t: str) -> int:\n",
    "        n,m=len(s),len(t)\n",
    "        sd=defaultdict(int)\n",
    "        td=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                sd[s[i:j+1]]+=1\n",
    "        for i in range(m):\n",
    "            for j in range(i,m):\n",
    "                td[t[i:j+1]]+=1\n",
    "        \n",
    "        ans=0\n",
    "        # print(sd)\n",
    "        # print(td)\n",
    "        for k,v in sd.items():\n",
    "            ck=len(k)\n",
    "            for tk,tv in td.items():\n",
    "                if len(tk)==ck:\n",
    "                    diff=0\n",
    "                    for i in range(ck):\n",
    "                        if k[i]!=tk[i]:\n",
    "                            diff+=1\n",
    "                    if diff==1:\n",
    "                        # print(k)\n",
    "                        # print(tk)\n",
    "                        ans+=v*tv \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
